17.1 KB · ⇊ 5 parts · ⤓ Micron 17.1 KB · ⤓ HTML 97.4 KB

top

Active-Set-Methoden sind eine Klasse iterativer Algorithmen zur Lösung von quadratischen Optimierungsproblemen.

• Mathematische Problemstellung

• Active Set

• Algorithmus

• Berechnung der Suchrichtung p k

• Berechnung der Lagrange-Multiplikatoren λ i

• Berechnung der Schrittlänge α k

• Literatur

• Einzelnachweise

Jedes quadratische Programm kann in eine standardisierte Form überführt werden:cite-ref-1[1]

min x ∈ ∈ R n 1 2 x T H x + c T x = f ( x ) s . t . a i T x ≥ ≥ b i ∀ ∀ i ∈ ∈ I a j T x = b j ∀ ∀ j ∈ ∈ E {\displaystyle {\begin{array}{rcl}\min _{x\in \mathbb {R} ^{n}}&{\frac {1}{2}}x^{T}Hx+c^{T}x&=f(x)\\s.t.&a_{i}^{T}x\geq b_{i}&\forall i\in {\mathcal {I}}\\&a_{j}^{T}x=b_{j}&\forall j\in {\mathcal {E}}\end{array}}}

wobei n {\displaystyle n} die Anzahl der Entscheidungsvariablen ist. In der Zielfunktion f ( x ) {\displaystyle f(x)} entspricht H {\displaystyle H} der Hesse-Matrix, die Mengen I {\displaystyle {\mathcal {I}}} und E {\displaystyle {\mathcal {E}}} indizieren die Ungleichheits- und Gleichheitsbedingungen. Oft wird dabei gefordert, dass die Matrix H {\displaystyle H} positiv semidefinit ist, da dann das Optimierungsproblem konvex ist.

Eine Nebenbedingung i ∈ ∈ I {\displaystyle i\in {\mathcal {I}}} ist aktiv an einem Punkt x {\displaystyle x} , wenn a i T x = b i {\displaystyle a_{i}^{T}x=b_{i}} gilt.

Das Active Set A ( x ) {\displaystyle {\mathcal {A}}(x)} ist die Menge aller aktiven Bedingungen an einem gültigen Punkt x {\displaystyle x} :

A ( x ) := { j ∈ ∈ E ∪ ∪ i ∈ ∈ I : a i T x = b i } {\displaystyle {\mathcal {A}}(x):=\{j\in {\mathcal {E}}\cup i\in {\mathcal {I}}:a_{i}^{T}x=b_{i}\}}

Active-Set-Methoden setzen eine initiale gültige Lösung x 0 {\displaystyle x_{0}} voraus. Die Algorithmen berechnen dann in jeder Iteration einen gültigen Punkt x k {\displaystyle x_{k}} , bis ein Optimum erreicht ist. Dabei wird eine Menge W k {\displaystyle W_{k}} verwaltet, die angibt, welche Nebenbedingungen in der aktuellen Iteration aktiv sein sollen.cite-ref-2[2]

Die Nebenbedingungen in W k {\displaystyle W_{k}} definieren einen Unterraum. Wenn x {\displaystyle x} in der optimalen Lösung der Zielfunktion in diesem Unterraum ist, kann man die Suchrichtung als p k = x − − x k {\displaystyle p_{k}=x-x_{k}} definieren. Substituiert man dies in die Zielfunktion, erhält man die Suchrichtung p k {\displaystyle p_{k}} durch Lösen eines quadratischen Subproblems:cite-ref-3[3]

min x ∈ ∈ R n 1 2 p k T H p k + g k T p k s . t . A T p k = 0 ∀ ∀ i ∈ ∈ W k {\displaystyle {\begin{array}{rcl}\min _{x\in \mathbb {R} ^{n}}&{\frac {1}{2}}p_{k}^{T}Hp_{k}+g_{k}^{T}p_{k}\\s.t.&A^{T}p_{k}=0&\forall i\in W_{k}\end{array}}}

wobei g k = H x k + c {\displaystyle g_{k}=Hx_{k}+c} der Gradient an der aktuellen Lösung ist und die Spalten der Matrix A {\displaystyle A} die Vektoren a i , i ∈ ∈ W k {\displaystyle a_{i},i\in W_{k}} sind.

Dieses Subproblem kann auf verschiedenen Weisen gelöst werden. Eine Möglichkeit ist dabei ein Nullspace-Ansatz:cite-ref-4[4]

Hat man eine Matrix Z {\displaystyle Z} , deren Spalten eine Basis für den Kern der Matrix A T {\displaystyle A^{T}} bilden, kann man den gültigen Bereich des Subproblems durch p k = Z u {\displaystyle p_{k}=Zu} parametrisieren. Löst man nun das Gleichungssystem

M u = − − Z T g k {\displaystyle Mu=-Z^{T}g_{k}} ,

wobei M = Z T H Z {\displaystyle M=Z^{T}HZ} die reduzierte Hesse-Matrix ist, erhält man die Suchrichtung im originalen Problem.

Falls die Suchrichtung p k = 0 {\displaystyle p_{k}=0} ist, ist x k {\displaystyle x_{k}} bereits optimal im aktuellen Unterraum. Man muss dann eine geeignete Ungleichheitsbedingung aus W k {\displaystyle W_{k}} entfernen. Die Lagrange-Multiplikatoren λ λ i {\displaystyle \lambda _{i}} erhält man durch Lösen eines linearen Gleichungssystems:

∑ ∑ i ∈ ∈ W k ∩ ∩ I a i λ λ i = g k = H x k + c {\displaystyle \sum _{i\in W_{k}\cap {\mathcal {I}}}a_{i}\lambda _{i}=g_{k}=Hx_{k}+c}

Falls alle λ λ i ≥ ≥ 0 {\displaystyle \lambda _{i}\geq 0} sind, erfüllen x k {\displaystyle x_{k}} und λ λ {\displaystyle \lambda } die Karush-Kuhn-Tucker-Bedingungen, welche notwendige Kriterien für die Optimalität sind. Wenn zudem die Hesse-Matrix H {\displaystyle H} positiv semidefinit ist, sind diese Bedingungen hinreichend und x k {\displaystyle x_{k}} ist die optimale Lösung des Problems. Entfernt man eine Ungleichheitsbedingung mit negativem Lagrange-Multiplikator aus W k {\displaystyle W_{k}} erhält man in der nächsten Iteration eine Suchrichtung.cite-ref-5[5]

Hat man eine Suchrichtung p k {\displaystyle p_{k}} , muss man die maximale Schrittlänge α α k {\displaystyle \alpha _{k}} berechnen. Eine volle Schrittlänge mit α α k = 1 {\displaystyle \alpha _{k}=1} führt direkt zum Minimum im durch W k {\displaystyle W_{k}} definierten Unterraum. Die Schrittlänge ist jedoch häufig durch eine Nebenbedingung i ∉ ∉ W k {\displaystyle i\notin W_{k}} beschränkt.

Alle Nebenbedingungen in i ∉ ∉ W k {\displaystyle i\notin W_{k}} mit a i T p k ≥ ≥ 0 {\displaystyle a_{i}^{T}p_{k}\geq 0} sind auch am Punkt x k + α α k p k {\displaystyle x_{k}+\alpha _{k}p_{k}} für alle α α k ≥ ≥ 0 {\displaystyle \alpha _{k}\geq 0} erfüllt, da dann die Ungleichung

a i T ( x k + α α k p k ) = a i T x k + α α k a i T p k ≥ ≥ a i T x k ≥ ≥ b i {\displaystyle a_{i}^{T}(x_{k}+\alpha _{k}p_{k})=a_{i}^{T}x_{k}+\alpha _{k}a_{i}^{T}p_{k}\geq a_{i}^{T}x_{k}\geq b_{i}}

gilt. Alle Nebenbedingungen i ∉ ∉ W k {\displaystyle i\notin W_{k}} mit a i T p k < 0 {\displaystyle a_{i}^{T}p_{k}<0} werden am neuen Punkt nur dann eingehalten, wenn für diese Nebenbedingungen die Ungleichung

a i T x k + α α k a i T p k ≥ ≥ b i {\displaystyle a_{i}^{T}x_{k}+\alpha _{k}a_{i}^{T}p_{k}\geq b_{i}}

gilt. Dies ist äquivalent mit der Bedingung

α α k ≤ ≤ b i − − a i T x k a i T p k ∀ ∀ { i ∉ ∉ W k | a i T p k < 0 } {\displaystyle \alpha _{k}\leq {\frac {b_{i}-a_{i}^{T}x_{k}}{a_{i}^{T}p_{k}}}\qquad \forall \{i\notin W_{k}|a_{i}^{T}p_{k}<0\}}

Um so nah wie möglich an das Optimum im aktuellen Unterraum zu kommen, kann man die maximale Schrittlänge durch diese Formel berechnen:

α α k = min ( 1 , min i ∉ ∉ W k , a i T p k < 0 b i − − a i T x k a i T p k ) {\displaystyle \alpha _{k}=\min(1,\min _{i\notin W_{k},a_{i}^{T}p_{k}<0}{\frac {b_{i}-a_{i}^{T}x_{k}}{a_{i}^{T}p_{k}}})}

Die Nebenbedingung, die diese Länge beschränkt, wird in die Menge W k + 1 {\displaystyle W_{k+1}} aufgenommen, da diese Nebenbedingung nun aktiv ist.cite-ref-6[6]

• Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, Kapitel 16.5.

• Roger Fletcher: Practical methods of optimization. Second Edition. John Wiley & Sons, 1987, ISBN 978-0-471-49463-8, Kapitel 10.3.

cite-note-11. ↑ Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 449.

cite-note-22. ↑ Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 472.

cite-note-33. ↑ Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 468.

cite-note-44. ↑ Roger Fletcher: Stable reduced Hessian updates for indefinite quadratic programming. Mathematical Programming (87.2) 2000, S. 251–264.

cite-note-55. ↑ Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 469f.

cite-note-66. ↑ Jorge Nocedal, Stephen J. Wright: Numerical Optimization. Second Edition. Springer, New York 2006, ISBN 978-0387-30303-1, S. 468f.